package com.mdnote.structure.sort;

import java.util.Arrays;

/**
 * @author Rhythm-2019
 * @version 1.0
 * @date 2020/8/26
 * @description 快速排序
 */
public class QuickSort {

    /**
     * 交换排序
     * @param source 原始数组
     * @param left 左边界
     * @param right 右边界
     */
    public static void sortBySwap(int[] source, int left, int right) {

        // 创建两个游标
        int leftCursor = left;
        int rightCurson = right;

        // 中轴
        int pivotvalue = source[(leftCursor + rightCurson) / 2];

        // 中间值
        int temp = 0;

        // 基本条件
        while (leftCursor < rightCurson) {
            // 目标：找到比较突出的元素
            while (source[leftCursor] < pivotvalue) {
                leftCursor++;
            }
            while (source[rightCurson] > pivotvalue) {
                rightCurson--;
            }
            // 如果左右游标相等，说明中轴左边的数全部小于右边的数字
            if (leftCursor == rightCurson) {
                break;
            }
            // 交换数字
            temp = source[leftCursor];
            source[leftCursor] = source[rightCurson];
            source[rightCurson] = temp;
        }
        // 游标最终都会指向同一个元素，我们需要把它岔开
        if (leftCursor == rightCurson) {
            leftCursor++;
            rightCurson--;
        }
        // 判断是否可以进行递归，当只有一个元素的时候不会进行递归
        if (left < rightCurson) {
            sortBySwap(source, left, rightCurson);
        }
        if (right > leftCursor) {
            sortBySwap(source, leftCursor, right);
        }
    }

    public static void main(String[] args) {
//        int[] data = {11, 66, 75, 12, 77};
        int[] data = {66, 55, 39, 44, 33};
        sortBySwap(data, 0, data.length - 1);
        System.out.println(Arrays.toString(data));
    }

    /**
     * 填坑
     * @param source 原始数组
     * @param left 左边界
     * @param right 右边界
     */
    public static void sortByPit(int[] source, int left, int right) {
        int leftCursor = left;
        int rightCursor = right;

        // 随便找一个基准值
        int refValue = source[left];
        while (leftCursor < rightCursor) {
            // 从右边找一个数来填0这个坑
            while (leftCursor < rightCursor && source[rightCursor] >= refValue) {
                rightCursor--;
            }
            if (leftCursor < rightCursor) {
                source[leftCursor] = source[rightCursor];
                leftCursor++;
            }
            // 从左边找一个数填到右边去
            while (leftCursor < rightCursor && source[leftCursor] < refValue) {
                leftCursor++;
            }
            if (leftCursor < rightCursor) {
                source[rightCursor] = source[leftCursor];
                rightCursor--;
            }
        }
        // 吧一开始的坑填了 最后i==j
        if (leftCursor == rightCursor) {
            source[leftCursor] = refValue;
        }

        // 左边递归
        if (left < leftCursor - 1) {
            sortByPit(source, left, leftCursor - 1);
        }
        if (right > leftCursor + 1) {
            sortByPit(source, rightCursor + 1, right);
        }
    }
}
